package ch2.part3;

/**
 * 循环队列的数组实现
 * 时间复杂度：
 * - 入队 O(n)=1
 * - 出队 O(n)=1
 * <p>
 * 无论出队入队，仅移动指针，不移动元素位置
 *
 * @author liuwanxiang
 * @version 2019/05/14
 */
public class MyCycleQueue {

    private Integer[] array;
    private int front;
    private int rear;

    public MyCycleQueue(int capacity) {
        this.array = new Integer[capacity];
    }

    /**
     * 入队
     * 时间复杂度：O(n)=1
     *
     * @param data
     */
    public void in(Integer data) {
        if ((rear + 1) % array.length == front) {
            throw new RuntimeException("队列已满~");
        }
        array[rear] = data;
        rear = (rear + 1) % array.length;
    }

    /**
     * 出队
     * 时间复杂度：O(n)=1
     *
     * @return
     */
    public Integer out() {
        if (rear == front) {
            throw new RuntimeException("队列为空~");
        }
        Integer rst = array[front];
        array[front] = null;
        front = (front + 1) % array.length;
        return rst;
    }

    public static void main(String[] args) {

        MyCycleQueue queue = new MyCycleQueue(5);
        queue.in(1);
        queue.in(2);
        queue.in(3);
        queue.in(4);

        System.out.println(queue.out());
        System.out.println(queue.out());
        System.out.println(queue.out());

        queue.in(5);
        queue.in(6);

    }


}
